#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
using namespace std;

const int N = 1e6 + 10, INF = 0x3f3f3f3f;

/*
按照右端点排序区间，离线处理
用last保存每个数字最后出现的位置，在下次在次出现时将上次的代价减去，保证不每种数字不会被重复统计
*/

int n, m;
int a[N], tr[N];
int ans[N], last[N];
struct node
{
    int l, r, id;
}q[N];

int lowbit(int x) { return x & -x; }
void add(int p, int x) { while (p <= n) { tr[p] += x, p += lowbit(p); } }
int ask(int p) { int sum = 0; for (;p;p -= lowbit(p)) sum += tr[p];return sum; }

void solve()
{
    cin >> n;
    for (int i = 1;i <= n;i++) cin >> a[i];
    cin >> m;
    for (int i = 1;i <= m;i++) {
        cin >> q[i].l >> q[i].r;
        q[i].id = i;
    }
    sort(q + 1, q + m + 1, [](const node& a, const node& b) {return a.r < b.r;});

    int tt = 1;
    for (int i = 1;i <= n;i++) {
        if (last[a[i]] != 0)
            add(last[a[i]], -1);
        add(i, 1);
        last[a[i]] = i;
        for (;tt <= m && q[tt].r <= i;tt++)
            ans[q[tt].id] = ask(q[tt].r) - ask(q[tt].l - 1);
    }
    for (int i = 1;i <= m;i++)
        cout << ans[i] << '\n';
}

signed main()
{
    // ios::sync_with_stdio(0);
    // cin.tie(0);
    int T = 1;
    //cin>>T;
    for (int i = 1;i <= T;i++) {
        solve();
    }
}

/*
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
using namespace std;

const int N = 1e6 + 10;

int n, m, block, ANS;
int a[N], pos[N], ans[N], cnt[N];
struct node {
    int l, r, k;
} q[N];

inline int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch>'9') {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
        x = x * 10 + ch - '0', ch = getchar();
    return x * f;
}

void write(int x)
{
    if (x < 0)
        putchar('-'), x = -x;
    if (x > 9)
        write(x / 10);
    putchar(x % 10 + '0');
    return;
}

bool cmp(node a, node b)
{
    if (pos[a.l] != pos[b.l])
        return pos[a.l] < pos[b.l];
    else if (pos[a.l] & 1) return a.r > b.r;
    return a.r < b.r;
}

signed main()
{
    n = read(); block = sqrt(n);
    for (int i = 1;i <= n;i++) {
        a[i] = read();
        pos[i] = (i - 1) / block + 1;
    }
    m = read();
    for (int i = 1;i <= m;i++) {
        q[i].l = read(); q[i].r = read();
        q[i].k = i;
    }
    sort(q + 1, q + m + 1, cmp);
    int l = 1, r = 0;
    for (int i = 1;i <= m;i++) {
        int ql = q[i].l, qr = q[i].r;
        while (l < ql) ANS -= !--cnt[a[l++]];
        while (l > ql) ANS += !cnt[a[--l]]++;
        while (r < qr) ANS += !cnt[a[++r]]++;
        while (r > qr) ANS -= !--cnt[a[r--]];
        ans[q[i].k] = ANS;
    }
    for (int i = 1; i <= m;i++) { write(ans[i]);putchar('\n'); }
}
*/